#include <iostream>
using namespace std;

// 记录过河方案的数量
int count = 0;

// 判断当前状态是否安全，即狼不会吃鸡，鸡不会吃谷子
bool IsSafe(int now[])
{
    // 检查狼会不会吃掉鸡
    if ((now[1] == now[2]) && (now[0] != now[1]))
        return false;
    // 检查鸡会不会吃掉谷子
    if ((now[2] == now[3]) && (now[0] != now[2]))
        return false;
    return true;
}

// 检查当前状态是否已经出现过（简单模拟备忘录功能）
bool isRepeated(int now[], int dira[], int a, int step)
{
    for (int i = 0; i < step; i++)
    {
        if (dira[i] == a)
            return true;
    }
    return false;
}

// 输出过河步骤的详细信息
void display(int dira[])
{
    for (int i = 0; i <= 17; i++)
    {
        cout << dira[i] << " ";
    }
    cout << endl;
}

// 根据记录的步骤信息输出具体的过河动作描述
void path(int dira[])
{
    int i = 0;
    while (dira[i] != 0)
    {
        int diff = dira[i] - dira[i + 1];
        switch (diff)
        {
        case 8:
        case -8:
            cout << "农夫独自过河" << endl;
            break;
        case 12:
        case -12:
            cout << "农夫带狼过河" << endl;
            break;
        case 10:
        case -10:
            cout << "农夫带鸡过河" << endl;
            break;
        case 9:
        case -9:
            cout << "农夫带谷子过河" << endl;
            break;
        default:
            cout << "未知动作" << endl;
            break;
        }
        i++;
    }
}

// 回溯法解决农夫过河问题的核心函数
void backtracking(int now[], int dira[], int step)
{
    // 将当前状态编码成一个整数，方便后续判断重复状态等操作
    int a = now[0] * 8 + now[1] * 4 + now[2] * 2 + now[3] * 1;
    // 剪枝操作，如果当前状态重复或者不安全则直接返回，不再继续探索该分支
    if (isRepeated(now, dira, a, step) || !IsSafe(now))
        return;

    dira[step] = a;

    // 判断是否所有物品都已成功运到对岸，若都在对岸则找到一种过河方案
    if (now[0] == 0 && now[1] == 0 && now[2] == 0 && now[3] == 0)
    {
        count++;
        cout << "过河的第" << count << "种方法" << endl;
        //        display(dira);
        path(dira);
        cout << endl;
        return;
    }

    // 尝试每种可能的移动方式，共4种（分别对应农夫单独或者带其他物品过河）
    for (int i = 0; i < 4; i++)
    {
        if (now[i] == now[0])
        { // 物体和农夫在同一侧才可以一起移动
            int temp[4];
            for (int j = 0; j < 4; j++)
            {
                temp[j] = now[j]; // 备份当前状态
            }

            now[i] = 1 - now[i]; // 移动物体，改变其所在位置（0表示对岸，1表示本岸）
            if (i != 0)
            {
                now[0] = 1 - now[0]; // 移动农夫
            }
            backtracking(now, dira, step + 1); // 递归调用，进入下一层探索
            for (int j = 0; j < 4; j++)
            {
                now[j] = temp[j]; // 恢复当前状态，回溯操作，以便尝试其他可能
            }
        }
    }
}

int main()
{
    int now[4] = {1, 1, 1, 1}; // 农夫、狼、鸡、谷子初始都在河的一侧
    int dira[18];
    for (int i = 0; i < 18; i++)
    {
        dira[i] = 0;
    }
    backtracking(now, dira, 0); // 调用回溯法函数开始求解
    return 0;
}
